import java.util.*;

public class Leetcode377 {
    Map<Integer, Integer> map = new HashMap<>();

    public int combinationSum4(int[] nums, int target) {
        if (nums.length == 1 && nums[0] > target) {
            return 0;
        }
//        dfs(nums,target,results,deque);
        return dfs(nums, target);
    }

    public int dfs(int[] nums, int target) {
        if (target == 0) {
            return 1;
        }
        if (map.containsKey(target)) {
            return map.get(target);
        }
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            if (target - nums[i] < 0) continue;
            res += dfs(nums, target - nums[i]);
        }
        map.put(target, res);
        return res;
    }
}
